#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <assert.h>

typedef int Key;

typedef int (*HashFunc)(Key, int);

typedef enum {
	EXISTED,
	DELETED,
	EMPTY
}	State;

typedef struct Element{
	Key key;
	State state;
}	Element;

typedef struct HashTable {
	Element *arr;
	int size;
	int capacity;
	HashFunc hashfunc;
}	HashTable;

void HashInit(HashTable *Hash, int capacity, HashFunc hashfunc)
{
	assert(Hash);
	Hash->arr = (Element *)malloc(sizeof(Element)*capacity);
	assert(Hash->arr);
	int i;
	for(i = 0 ; i < capacity ; i++) {
		Hash->arr[i].state = EMPTY;
	}

	Hash->size = 0;
	Hash->capacity = capacity;
	Hash->hashfunc = hashfunc;
}

int Search(HashTable *Hash, Key key)
{
	int index = Hash->hashfunc(key, Hash->capacity);
	int iCount;
	while(Hash->arr[index].state != EMPTY) {
		if(Hash->arr[index].key == key && Hash->arr[index].state == EXISTED) {
			return 1;
		}

		//缺点 容易出现死循环
		index = (index + 1) % Hash->capacity;
		iCount++;
	}
	return -1;
}

void ExpandIfNeed(HashTable *Hash);

int Insert(HashTable *Hash, Key key)
{
	ExpandIfNeed(Hash);

	int iCount = 1;
	int index = Hash->hashfunc(key, Hash->capacity);
	int i = index;

	while(Hash->arr[i].state == EXISTED) {
		if(Hash->arr[i].key == key && Hash->arr[i].state == EXISTED) {
			return -1;
		}

		i = (i + iCount*iCount) % Hash->capacity;
		iCount++;
	}

	Hash->arr[i].key = key;
	Hash->arr[i].state = EXISTED;
	Hash->size++;
//	while(Hash->arr[index].state != EMPTY) {
//		if(Hash->arr[index].state == DELETED) {
//			Hash->arr[index].key = key;
//			Hash->arr[index].state = EXISTED;
//			return 1;
//		}
//
//		if(Hash->arr[index].key == key && Hash->arr[index].state == EXISTED) {
//			Hash->arr[index].key = key;
//			return 1;
//		}
//
//		index = (index + 1) % Hash->capacity;
//	}
//
//	Hash->arr[index].key = key;
//	Hash->arr[index].state = EXISTED;

	return 1;
}

void ExpandIfNeed(HashTable *Hash)
{
	assert(Hash);
	if(Hash->size * 10 / Hash->capacity < 7) {
		return;
	}

	HashTable newHash;
	HashInit(&newHash, Hash->capacity * 2, Hash->hashfunc);

	int i = 0;
	for(i = 0 ; i < newHash.capacity ; i++) {
		if(Hash->arr[i].state == EXISTED) {
			Insert(&newHash, Hash->arr[i].key);
		}
	}

	free(Hash->arr);
	Hash->arr = newHash.arr;
	Hash->capacity = newHash.capacity;
}

//删除------假删除
int Remove(HashTable *Hash, Key key)
{
	assert(Hash);

	int index = Hash->hashfunc(key, Hash->capacity);
	while(Hash->arr[index].state != EMPTY) {
		if(Hash->arr[index].key == key && Hash->arr[index].state == EXISTED) {
			Hash->arr[index].state = DELETED;
			Hash->size--;
			return 1;
		}

		index = (index + 1) % Hash->capacity;
	}
	return -1;
}

void Destory(HashTable *Hash)
{
	free(Hash->arr);
	Hash->arr = NULL;
}

int chuliuyushufa(Key key, int capacity) {
	return key % capacity; 
}

void HashPrint(HashTable *Hash)
{
	assert(Hash);

	int index = 0;
	for(index = 0 ; index < Hash->capacity ; index++) {
		printf("key : %d	index : %d\n", Hash->arr[index].key, index);
	}
}

int main()
{
	HashTable Hash;
	HashInit(&Hash, 13, chuliuyushufa);
	Insert(&Hash, 3);
	Insert(&Hash, 7);
	Insert(&Hash, 19);
	Insert(&Hash, 25);
	Insert(&Hash, 26);
	Insert(&Hash, 6);
	Insert(&Hash, 12);
	Insert(&Hash, 39);
	Insert(&Hash, 41);
	Insert(&Hash, 32);
	Insert(&Hash, 45);

	HashPrint(&Hash);
}
